class PrimeCircleSolution:
    # 本题中需要反复检查两数之和是否为素数，而且范围为20以内的数相加
    # 因此考虑用打表法提高查找效率
    def __init__(self) -> None:
        self.primes = [True] * 40
        for i in range(2, 40):
            if self.primes[i]:
                for j in range(i + i, 40, i):
                    self.primes[j] = False
    
    # 工具方法：判断x是否素数
    def isPrime(self, x: int) -> bool:
        return self.primes[x]
        
    # 回溯法求解素数环问题
    def primeCircle(self, n: int):
        # 用数组表示素数环，并初始化为0
        a = [0] * n

        # 定义k为第一个位置，并从位置0填写1开始搜索
        a[0] = 1         
        k = 1   

        # 执行DFS     
        while k >= 1:
            # 不断试探下一个数，直到符合题目规则
            a[k] = a[k] + 1
            while a[k] <= n:
                if self.check(k, a, n):
                    break   
                else:
                    a[k] = a[k] + 1 

            # 找到结果时，直接输出并返回
            if a[k] <= n and k == n - 1:
                print('  '.join(map(str, a)))
                return

            # 填写下一个位置，或者回溯上一个位置
            if a[k] <= n and k < n - 1:
                k += 1     
            else: 
                a[k] = 0
                k -= 1

    # 检查当前填写是否满足素数环规则
    def check(self, k: int, a: list[int], n: int) -> bool:
        # flag为true表示正常向下一级移动，false表示回溯到上一级
        flag = False  
        # 判断是否重复
        if any(x == a[k] for x in a[:k]):
            return flag
        # 判断相邻数之和是否素数
        flag = self.isPrime(a[k] + a[k - 1])  
        #判断第一个和最后一个是否素数 
        if flag and k == n - 1:
            flag = self.isPrime(a[k] + a[0])  
        return flag

# main
sln = PrimeCircleSolution()
sln.primeCircle(20)

